package leetcode.editor.cn;

import java.util.*;

/**
 * @id: 36
 * @title: 有效的数独
 */
 
//请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 
// 
//
// 
//
// 注意： 
//
// 
// 一个有效的数独（部分已被填充）不一定是可解的。 
// 只需要根据以上规则，验证已经填入的数字是否有效即可。 
// 空白格用 '.' 表示。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：board = 
//[["5","3",".",".","7",".",".",".","."]
//,["6",".",".","1","9","5",".",".","."]
//,[".","9","8",".",".",".",".","6","."]
//,["8",".",".",".","6",".",".",".","3"]
//,["4",".",".","8",".","3",".",".","1"]
//,["7",".",".",".","2",".",".",".","6"]
//,[".","6",".",".",".",".","2","8","."]
//,[".",".",".","4","1","9",".",".","5"]
//,[".",".",".",".","8",".",".","7","9"]]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：board = 
//[["8","3",".",".","7",".",".",".","."]
//,["6",".",".","1","9","5",".",".","."]
//,[".","9","8",".",".",".",".","6","."]
//,["8",".",".",".","6",".",".",".","3"]
//,["4",".",".","8",".","3",".",".","1"]
//,["7",".",".",".","2",".",".",".","6"]
//,[".","6",".",".",".",".","2","8","."]
//,[".",".",".","4","1","9",".",".","5"]
//,[".",".",".",".","8",".",".","7","9"]]
//输出：false
//解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无
//效的。 
//
// 
//
// 提示： 
//
// 
// board.length == 9 
// board[i].length == 9 
// board[i][j] 是一位数字（1-9）或者 '.' 
// 
// Related Topics 数组 哈希表 矩阵 
// 👍 734 👎 0

public class P36ValidSudoku {
    public static void main(String[] args) {
        Solution solution = new P36ValidSudoku().new Solution();
        // todo
        char[][] b = new char[][]{
                {'.', '.', '.', '.', '5', '.', '.', '1', '.'},
                {'.', '4', '.', '3', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '3', '.', '.', '1'},
                {'8', '.', '.', '.', '.', '.', '.', '2', '.'},
                {'.', '.', '2', '.', '7', '.', '.', '.', '.'},
                {'.', '1', '5', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '2', '.', '.', '.'},
                {'.', '2', '.', '9', '.', '.', '.', '.', '.'},
                {'.', '.', '4', '.', '.', '.', '.', '.', '.'}
        };
        final boolean validSudoku = solution.isValidSudoku(b);
        System.out.println(validSudoku);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    // 代码改进，使用状态位检查碰撞
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] clus = new int[9][9];
        int[][] palaces = new int[9][9];
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                // 宫格编号(i/3)*3+j/3
                int palaceIdx = (r / 3) * 3 + c / 3;
                if (board[r][c] != '.') {
                    int idx = board[r][c] - '0' - 1;
                    rows[r][idx] += 1;
                    clus[c][idx] += 1;
                    palaces[palaceIdx][idx] += 1;
                    if (rows[r][idx] > 1 || clus[c][idx] > 1 || palaces[palaceIdx][idx] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

/*

    // 行列及所处3x3宫内不能存在重复数字
    // 通过预处理记录每个宫和行列是否存在碰撞
    public boolean isValidSudoku(char[][] board) {
       // 把3x3都拿出来
        Map<Integer, Set<Character>> palace = new HashMap<>();
        Map<Integer, Set<Character>> rows = new HashMap<>();
        Map<Integer, Set<Character>> clus = new HashMap<>();
        for (int i = 0; i < 9; ++i) {
            // 当前行是不是已经记录过
            if (!rows.containsKey(i)) {
                Set<Character> row = new HashSet<>();
                for (int clu = 0; clu < board.length; ++clu) {
                    if (row.contains(board[i][clu])) {
                        return false;
                    }
                    if (board[i][clu] != '.') {
                        row.add(board[i][clu]);
                    }
                }
                rows.put(i, row);
            }
            // 遍历列
            for (int j = 0; j < 9; ++j) {
                // 判断
                if (!clus.containsKey(j)) {
                    Set<Character> clu = new HashSet<>();
                    for (int row = 0; row < board.length; ++row) {
                        if (clu.contains(board[row][j])) {
                            return false;
                        }
                        if (board[row][j] != '.')
                            clu.add(board[row][j]);
                    }
                    clus.put(j, clu);
                }

                if (!getPalace(board, palace, i, j)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean getPalace(char[][] board, Map<Integer, Set<Character>> palace, int x, int y) {
        // 进入宫起点，遍历宫
        int palaceKey = x * 10 + y;
        if (x % 3 == 0 && y % 3 == 0
                && !palace.containsKey(palaceKey)) {
            Set<Character> pl = new HashSet<>();
            for (int i = x; i < x + 3; ++i) {
                for (int j = y; j < y + 3; ++j) {
                    if (pl.contains(board[i][j])) {
                        return false;
                    }
                    if (board[i][j] != '.') {
                        pl.add(board[i][j]);
                    }
                }
            }
            palace.put(palaceKey, pl);
        }
        return true;
    }
*/

    }
//leetcode submit region end(Prohibit modification and deletion)


}